package com.algorithm.pack;

import org.junit.Before;
import org.junit.Test;

public class TestZeroOnePack {

    int[] weight;
    int[] value;
    int volume;
    int N;

    @Before
    public void initData(){
        weight = new int[]{10,20,30};
        value = new int[]{60,100,120};
        volume = 50;//背包容积
        N = 3;      //物品个数
    }

    @Test
    public void testZeroOnePack_recursive(){
        int max_value = ZeroOnePack.zeroOnePack_recursive(N,weight,value,volume);

        System.out.println("The max value is:"+max_value);

        int remain_space = volume;

        for(int i=N;i>=1;i--){
            if(remain_space>=weight[i-1]){
                int value1 = ZeroOnePack.zeroOnePack_recursive(N,weight,value,remain_space);
                int value2 = ZeroOnePack.zeroOnePack_recursive(N-1,weight,value,remain_space-weight[i-1]);
                if(value1-value2 == value[i-1]){
                    System.out.println("The item "+i+" is selected.");
                    remain_space -= weight[i-1];
                }
            }
        }
    }

    @Test
    public void testZeroOnePack_space(){
        int F[] = ZeroOnePack.zeroOnePack_space(weight,value,volume);

        Tools.printArray(F);

        System.out.println("The max value is:"+F[volume]);
    }

    @Test
    public void testZeroOnePack(){
        int F[][] = ZeroOnePack.zeroOnePack(weight,value,volume);//最优解矩阵

        Tools.printArray(F);

        System.out.println("The max value is:"+F[N][volume]);

        int remain_space = volume;//背包剩余空间

        //输出所选择的物品列表
        for(int i=N;i>=1;i--){
            //从物品N-->物品1检索
            if(remain_space>=weight[i-1]){
                //剩余空间不小于当前物品重量
                if(F[i][remain_space]-F[i-1][remain_space-weight[i-1]]==value[i-1]){
                    System.out.println("The item "+i+" is selected.");
                    remain_space -= weight[i-1];
                }
            }
        }
    }
}
